package com.Leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.Util.ProduceTree;
import com.structure.TreeNode;

public class Index652findDuplicateSubtrees {
	List<TreeNode> ans = null;
	Map<String,Integer> map = new HashMap<>();
	public static void main(String[] args) {
		String node = "[0,0,0,0,null,null,0,null,null,null,0]";
		TreeNode root = ProduceTree.stringToTreeNode(node);
		Index652findDuplicateSubtrees subtrees = new Index652findDuplicateSubtrees();
		List<TreeNode> ans = subtrees.findDuplicateSubtrees(root);
		for(TreeNode tree : ans)
			System.out.println(ProduceTree.treeNodeToString(tree));
	}
	
	public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
		ans = new ArrayList<>();
		duplicateSubtrees(root);
		return ans;
    }
	
	String duplicateSubtrees(TreeNode root){
		if(root == null) return ",";
		String left = duplicateSubtrees(root.left);
		String right = duplicateSubtrees(root.right);
		
		String subTree = left+","+root.val+","+right;
		int res = map.getOrDefault(subTree, 0);
		if(res == 1)
			ans.add(root); 
		map.put(subTree,res+1);
		return subTree;
	}
	
}
